package com.zdp.leetcodeMiddle;

public class 秋叶收藏集 {
    /*
    * 题目描述：
    * 小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves， 字符串 leaves 仅包含小写字符 r 和 y，
    * 其中字符 r 表示一片红叶，字符 y 表示一片黄叶。
    * 出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。
    * 每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。
    * 请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。
    示例 1：
    输入：leaves = "rrryyyrryyyrr"
    输出：2
    解释：调整两次，将中间的两片红叶替换成黄叶，得到 "rrryyyyyyyyrr"
    示例 2：
    输入：leaves = "ryr"
    输出：0
    解释：已符合要求，不需要额外操作
    提示：
    3 <= leaves.length <= 10^5
    leaves 中只包含字符 'r' 和字符 'y'
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/UlBDOe
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    * */
    public static void main(String[] args) {
        秋叶收藏集 demo = new 秋叶收藏集();
        demo.minimumOperations("rrryyyrryyyrr");
        System.out.println(demo.minimumOperations1("rrryyyrryyyrr"));
    }
    /*
    * 使用动态规划
    * 将 字符串分为3部分  用三个状态来表示 0 1 2
    * 0 : 从第0个字符开始 都是红色的 ===> f[0][i] ===>对第0-i个字符进行修改，使得0-i字符保持 红 状态，需要修改的最小次数
    * 所以 f[0][i] = f[0][i-1] + if(i is yellow)?1:0  ===> 最小的修改次数 = i-1的最小次数 + 第i个字符的修改次数（0或1）
    * 1:  f[1][i] ===>表示对第0-i个字符进行修改，使得0-i字符保持 红 黄 状态   所以第i个字符前面 既可以是0状态，也可以是1状态
    * 所以 f[1][i] = Min{f[0][i-1],f[1][i-1]} + if(i is yellow)?0:1
    * 2: f[2][i] ===>表示对第0-i个字符进行修改，使得0-i字符保持 红 黄 红状态，所以第i个字符前面 既可以是1状态，也可以是2状态
    * 所以 f[2][i] = Min{f[1][i-1],f[2][i-1]} + if(i is yellow)?1:0
    * 因为是动态规划，所以要找到不被依赖的项
    * 分析不被依赖的项  因为每个状态都至少有一个字符 ，所以 在1状态下，至少得有两个字符，在2状态下，至少得有3个字符
    * 因此得出 f[1][0] = f[2][0] = f[2][1] = 不存在（用最大值表示，因为我们取得都是最小值）
    * f[0][0] 的次数 则取决于 第一个字符的颜色 f[0][0] = if(0 is yellow)?1:0
    * */
    //不要在题解里面弄一些没用的输出，会™超时
    public int minimumOperations(String leaves) {
        int[][] f = new int[3][leaves.length()];
        f[0][0] = leaves.charAt(0)=='y'?1:0;
        f[1][0] = f[2][0] = f[2][1] = Integer.MAX_VALUE;
        //初始化一下 dp表
        //开始规划
        for(int i=1;i<leaves.length();i++){
            //先计算 0 状态
            f[0][i] = f[0][i-1] + (leaves.charAt(i)=='y'?1:0);
            //再计算1状态
            f[1][i] = (leaves.charAt(i)=='y'?0:1) + Math.min(f[0][i-1],f[1][i-1]);
            //最后计算2状态
            //2状态至少要有3个字符
            if(i>=2){
                f[2][i] = (leaves.charAt(i)=='y'?1:0 )+ Math.min(f[1][i-1],f[2][i-1]);
            }

        }
        return f[2][leaves.length()-1];
    }
    //优化空间
    //因为上面的数组 i 都是在 i-1的基础上来的 而i-1 也只用于i
    //所以并不需要用数组来进行存储，只要用一个变量和一个暂存变量 用来记录i-1的值就行了
    //变量和暂存变量一起更新
    public int minimumOperations1(String leaves) {
        //利用三个状态变量代替状态数组
        int one = 0;
        int two = Integer.MAX_VALUE;
        int three = Integer.MAX_VALUE;
        one = leaves.charAt(0)=='y'?1:0;
        for(int i=1;i<leaves.length();i++){
            int temp = one;
            one = one + (leaves.charAt(i)=='y'?1:0);
            int temp2 = two;
            two = (leaves.charAt(i)=='y'?0:1) + Math.min(temp,two);
            if(i>=2){
                three = (leaves.charAt(i)=='y'?1:0)+ Math.min(temp2,three);
            }
        }
        return three;
    }
    /*
    * 解法2： 关于前缀和+动态规划 ====> 就是数学推导
    * 还是把 字符串分为三个区间 0-x  x+1-y  y+1-n-1
    * 那么要操作的次数就等于： 0-x（所有黄色的叶子数）+ x+1-y(所有红色的叶子数) + y+1-n-1(所有黄色的叶子数）
    * 如果要枚举 x 和 y  ===> 时间复杂度达到o(n^2) ===>超时
    * 所以要进行优化  只枚举一个变量  利用前缀和 来进行算式的优化
    * preY preR ===> 前缀和
    * 则 第一个阶段 可以表示为 preY(x)
    * 第二个阶段，则可以表示为 preR(y)-preR(x)
    * 第三个阶段： preY(n-1) - preY(y)
    * 因为 preY(n-1) 为常量  preR(y) preY(y) 可以计算  ===>所以我们只需要搞到最小的preY(x)-preR(x)即可
    * 还有一个重要的式子 : preY(i)+preR(i) = i+1
    * 具体的算式优化看官方题解把
    *
    * */
    public int minimumOperations2(String leaves) {
        int n = leaves.length();
        int g = leaves.charAt(0) == 'y' ? 1 : -1;
        int gmin = g;
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i < n; ++i) {
            int isYellow = leaves.charAt(i) == 'y' ? 1 : 0;
            g += 2 * isYellow - 1;
            if (i != n - 1) {
                ans = Math.min(ans, gmin - g);
            }
            gmin = Math.min(gmin, g);
        }
        return ans + (g + n) / 2;
    }

}
